package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

/**
 * 牛顿插值多项式实现
 */
public class NewtonInterpolation {

    /**
     * 生成牛顿基多项式 (x - x0)(x - x1)...(x - xn-1)
     * @param data 插值节点 [[x0,y0], [x1,y1], ...]
     * @param n 基多项式阶数（n=0返回1，n=1返回(x - x0)，n=2返回(x - x0)(x - x1)）
     * @return 基多项式系数（索引0为最高次项，索引末尾为常数项）
     */
    private static List<Double> getPolynomial(List<List<Double>> data, int n) {
        int dataSize = data.size();
        List<Double> arr = new ArrayList<>();
        for (int i = 0; i < dataSize; i++) {
            arr.add(0.0);
        }

        if (n == 0) {
            arr.set(dataSize - 1, 1.0); // 常数项1，对应多项式 1
            return arr;
        }

        // 构建一次多项式矩阵：每行 [1, -x_i] 对应 (1 - x_i * x) = -(x - x_i)
        List<List<Double>> matrix = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            double xi = data.get(i).get(0);
            matrix.add(List.of(1.0, -xi));
        }

        // 多项式乘法展开
        List<Double> p = PolynomialUtils.polynomialSimplify(matrix);
        // 前面补0，使长度等于dataSize
        return PolynomialUtils.padZero(p, dataSize);
    }

    /**
     * 牛顿插值核心方法
     * @param data 插值节点 [[x0,y0], [x1,y1], ..., [xn,yn]]
     * @return 插值多项式（霍纳形式）
     */
    public static HornerPolynomial interpolate(List<List<Double>> data) {
        int size = data.size();
        // 步骤1：生成牛顿基多项式数组 e
        List<List<Double>> e = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            e.add(getPolynomial(data, i));
        }

        // 步骤2：计算差商表 f
        // f[i][j] 表示 j 阶差商，i 表示起始节点索引
        List<List<Double>> f = new ArrayList<>();
        for (int index = 0; index < size; index++) {
            List<Double> row = new ArrayList<>();
            for (int j = 0; j < size - index; j++) {
                row.add(0.0);
            }
            f.add(row);
        }

        // 初始化0阶差商（函数值）
        for (int i = 0; i < size; i++) {
            f.get(i).set(0, data.get(i).get(1));
        }

        // 计算高阶差商
        for (int i = 0; i < size; i++) {
            for (int j = 1; j <= i; j++) {
                double f1 = f.get(i - j + 1).get(j - 1);
                double f2 = f.get(i - j).get(j - 1);
                double xi = data.get(i).get(0);
                double xj = data.get(i - j).get(0);
                double diffQuotient = (f1 - f2) / (xi - xj);
                f.get(i - j).set(j, diffQuotient);
            }
        }

        // 步骤3：求和生成最终多项式系数
        List<Double> polynomial = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            polynomial.add(0.0);
        }

        for (int i = 0; i < size; i++) {
            double fi0 = f.get(0).get(i); // 0阶起始的i阶差商
            List<Double> ei = e.get(i);   // 第i个基多项式
            // 同幂次系数相加
            for (int j = 0; j < size; j++) {
                double val = polynomial.get(j) + fi0 * ei.get(j);
                polynomial.set(j, val);
            }
        }

        // 返回霍纳多项式
        return new HornerPolynomial(polynomial);
    }

    // 测试方法
    public static void main(String[] args) {
        // 测试数据：[[0,1],[2,5],[4,17]] → 对应多项式 x² + 1
        List<List<Double>> data = new ArrayList<>();
        data.add(List.of(0.0, 1.0));
        data.add(List.of(2.0, 5.0));
        data.add(List.of(4.0, 17.0));

        HornerPolynomial polynomial = NewtonInterpolation.interpolate(data);

        // 输出测试结果
        System.out.printf("%.1f %.1f %.1f%n",
                polynomial.apply(0.0),
                polynomial.apply(2.0),
                polynomial.apply(4.0));

        System.out.printf("%.1f %.1f %.1f%n",
                polynomial.apply(1.0),
                polynomial.apply(3.0),
                polynomial.apply(5.0));

        System.out.println(polynomial);
        System.out.println(polynomial.getPolynomial());
    }
}